package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      给定一个二进制数组， 计算其中最大连续1的个数。
 *
 * 2. 算法分析
 *      1. 滑动窗口法
 *          从具体的例子开始分析:[1,1,0,1,1,1],从例子中我们看出最大连续1长度为3
 *          设置左右窗口为left和right，设置一个额外的变量zeros来记录当前0出现的
 *          次数
 *          如果当前右窗口对应的元素为0，则zeros++，然后移动右窗口
 *          如果当前右窗口对应的元素为1，则直接移动右窗口
 *          每次移动完右窗口之后，我们需要判断当前窗口中的0元素是否大于0，
 *          如果当前窗口的0元素为0，说明没有0，此时的窗口为连续1的子数组
 *          此时只需要直接更新最大连续1的长度即可
 *          如果当前窗口的0元素大于0，说明当前窗口有0元素，此时0元素的位置有两种
 *          1、 在左窗口
 *          2. 在窗口的中间位置(此时是一个左闭右开的区间，不包含有窗口边界的)
 *          如果是左窗口我们需要移动left，然后zeros--，移动这个0元素被移动出去了
 *          如果在中间位置，直接移动left即可，知道窗口内没有0元素
 *
 *     2. 一次遍历法  优化上述解法，上面的时间复杂度最好为O(n),最坏为O(n^2)
 *        一次遍历的时间复杂度为O(n)
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q015_最大连续1的长度 {
    // 滑动窗口
    public int findMaxConsecutiveOnes1(int[] nums) {
        int n = nums.length;
        int zeros = 0;
        int left = 0;
        int right = 0;
        int max = 0;
        while(right < n) {
            if (nums[right] == 0) {
                zeros++;
            }
            right++;
            while(zeros > 0) {
                if (nums[left] == 0) {
                    left++;
                    zeros--;
                } else {
                    left++;
                }
            }
            max = Math.max(max,right-left);
        }
        return max;
    }

    // 一次扫描
    public int findMaxConsecutiveOnes2(int[] nums) {
        int zeros = 0;
        int ones = 0; // 当前最大
        int maxOnes = 0; // 全局最大
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            if(nums[i] == 1) {
                ones++;
            } else {
                maxOnes = Math.max(maxOnes,ones);
                ones = 0; // 清0
            }
        }
        maxOnes = Math.max(maxOnes,ones); // 注意for循环走完之后还需要一次max更新，否则可能会漏掉最后找到的一次
        return maxOnes;
    }
}
